package ordinaryArray;

/**
 * @author kunkun
 * @className LeetCode_53
 * @Description 返回最大和的连续子数组
 * @date 2025/3/4 13:52
 */
public class LeetCode_53 {

    public int maxSubArray(int[] nums) {
        return solution_1(nums);
    }

    public static void main(String[] args) {
        LeetCode_53 object = new LeetCode_53();
        System.out.println(object.maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4}));//6
        System.out.println(object.maxSubArray(new int[]{1}));//1
        System.out.println(object.maxSubArray(new int[]{5,4,-1,7,8}));//23
        System.out.println(object.maxSubArray(new int[]{-2,1}));//1
        System.out.println(object.maxSubArray(new int[]{-1}));//-1

    }


    /**
    * @Description: 方法1：前缀和求解 时间复杂度：O（n），空间复杂度：O（1）
    * @Author: kunkun
    * @Date:  2025/3/4 14:08
    * @Parameters:
    * @Return
    * @Throws
    */
    public int solution_1(int[] nums){
        //1. 定义最小前缀和，前缀和，返回结果
        int minPre=0;
        int sum = 0,result=nums[0];

        //2. 循环遍历
        for (int i = 0; i < nums.length; i++) {
            //2.1 计算前缀和，记录最小前缀和
            sum+=nums[i];

            //2.2 返回结果
            if (result<sum-minPre){
                result= sum-minPre;
            }

            //2.3 记录最小min
            if (sum<minPre){
                minPre = sum;
            }

        }

        return result;
    }

    /**
     * @description 动态规划求解
     * @author hkfan
     * @time 2025/6/26 16:33
     */
    public int maxSubArray2(int[] nums) {
        if (nums.length==0){
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0]=nums[0];
        int res = dp[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
            res=Math.max(res,dp[i]);
        }
        return res;
    }





}
